package offer.linkedList;

/**
 * 题目：在O(1)时间内删除链表节点
 * https://github.com/CyC2018/CS-Notes/blob/master/notes/18.1%20%E5%9C%A8%20O(1)%20%E6%97%B6%E9%97%B4%E5%86%85%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E8%8A%82%E7%82%B9.md
 *
 * @author DengYuan2
 * @create 2021-02-21 20:42
 */
public class n_18_1 {
    public static void main(String[] args) {
        n_18_1 n = new n_18_1();
        ListNode n1 = new ListNode(67);
        ListNode n2 = new ListNode(0);
        ListNode n3 = new ListNode(24);
        ListNode n4 = new ListNode(58);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        ListNode res = n.deleteNode2(n1, n1);
        System.out.println(res);
    }

    /**
     * 我的这个写法不太符合题意哦，不是那个意思，理解错了题，不用查找那个tobeDelete节点啊
     * 而且时间复杂度也没达到要求
     *
     * @param head
     * @param tobeDelete
     * @return
     */
    public ListNode deleteNode(ListNode head, ListNode tobeDelete) {
        ListNode dumbHead = new ListNode(-1);
        dumbHead.next = head;
        ListNode curNode = dumbHead;
        while (curNode.next != null && curNode.next.val != tobeDelete.val) {
            curNode = curNode.next;
        }
        curNode.next = curNode.next.next;
        return dumbHead.next;
    }

    /**
     * 思路：
     * ① 如果该节点不是尾节点，那么可以直接将下一个节点的值赋给该节点，
     * 然后令该节点指向下下个节点，再删除下一个节点，时间复杂度为 O(1)。
     * ② 否则，就需要先遍历链表，找到节点的前一个节点，然后让前一个节点
     * 指向 null，时间复杂度为 O(N)
     * 综上，如果进行 N 次操作，那么大约需要操作节点的次数为 N-1+N=2N-1，
     * 其中 N-1 表示 N-1 个不是尾节点的每个节点以 O(1) 的时间复杂度操作
     * 节点的总次数，N 表示 1 个尾节点以 O(N) 的时间复杂度操作节点的总次数。
     * (2N-1)/N ~ 2，因此该算法的平均时间复杂度为 O(1)
     *
     * @param head
     * @param tobeDelete
     * @return
     */
    public ListNode deleteNode2(ListNode head, ListNode tobeDelete) {
        if (head == null || tobeDelete == null) {
            return null;
        }
        //如果要删除最后一个节点，就要找到它的前一个节点
        if (tobeDelete.next == null) {
            //如果就只有1个节点，且要删除该节点，则之间返回null
            if (head == tobeDelete) {
                return null;
            }
            ListNode curNode = head;
            while (curNode.next != tobeDelete) {
                curNode = curNode.next;
            }
            curNode.next = null;

        } else {
            ListNode next = tobeDelete.next;
            tobeDelete.val = next.val;
            tobeDelete.next = next.next;
        }
        return head;
    }
}
